package 力扣._416_分割等和子集;

import java.util.Arrays;

public class Solution {
    public boolean canPartition(int[] nums) {
        //将元素分为两个子集，子集的和相同， sum为nums和
        //让背包容量为sum/2,物品重量与价值等价（这样最大价值就是最大容量），每个元素只能使用一次-》0/1背包
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0)
            return false;
        int m = sum / 2;//背包容量
        int[] dp = new int[m + 1];
        //初始化
        dp[0] = 0;
        for (int j = 0; j <= m; j++) {
            if (j >= nums[0])
                dp[j] = nums[0];
        }

        for (int i = 1; i < nums.length; i++) { //物品
            for (int j = m; j >= nums[i]; j--) {    //背包
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
//        System.out.println(Arrays.toString(dp));
        return dp[m] == m;
    }

    public static void main(String[] args) {
        boolean b = new Solution().canPartition(new int[]{1,2,5});
        System.out.println(b);
    }
}
